/**
 * @file lrd.c
 * @author 黄志烨 (matsuri@bupt.edu.cn)
 * @brief 二叉树的中序后序求先序
 * @version 0.1
 * @date 2022-04-27
 * 
 * @copyright Copyright (c) 2022
 * 
 */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef char ElementType;
typedef struct TreeNode *BinTree;
typedef BinTree Position;
struct TreeNode
{
    ElementType element;
    BinTree Left;
    BinTree Right;
};

void Visit(BinTree bt);

/**
 * @brief 题解
 * 
 * @param inOrder 
 * @param postOrder 
 * @return char* 
 */
char *Ird(char inOrder[], char postOrder[]);

/**
 * @brief 解题程序——递归
 * 
 * @param inOrder 
 * @param postOrder 
 * @param size 
 * @return struct TreeNode* 
 */
struct TreeNode *recSolution(char inOrder[], char postOrder[], int size);

/**
 * @brief 求字符串长度
 * 
 * @param str 目标字符串
 * @return int 字符串长度
 */
int length(char str[]);

/**
 * @brief Create a Tree Node object
 * 
 * @param item  字符
 * @return struct TreeNode* 树节点
 */
struct TreeNode *createTreeNode(ElementType item);

// void PreOrderTravel(BinTree BT){
//     if(BT){
//         Visit(BT);
//         PreOrderTravel(BT->Left);
//         PreOrderTravel(BT->Right);
//     }
// }

// void Visit(BinTree bt){
//     printf("%c",bt->element);
// }

int length(char str[]) {
    int i = 0;
    while (str[i] != 0)
    {
        i++;
    }

    return i;
    
}

struct TreeNode *createTreeNode(ElementType item) {
    BinTree t = (BinTree) malloc(sizeof(BinTree));
    t->element = item;
    t->Left = t->Right = NULL;
    return t;
}

struct TreeNode *recSolution(char inOrder[], char postOrder[], int size) {
    if (size == 0) return NULL;
    BinTree root = createTreeNode(postOrder[size - 1]);
    int inRootPos;
    for (inRootPos = 0; inOrder[inRootPos] != postOrder[size - 1]; inRootPos++);
    root->Left = recSolution(inOrder, postOrder, inRootPos);
    root->Right = recSolution(inOrder + inRootPos + 1, postOrder + inRootPos, size - inRootPos - 1);
    return root;
}

char *Ird(char inOrder[], char postOrder[]) {
    BinTree t = recSolution(inOrder, postOrder, length(inOrder));
    PreOrderTravel(t);
    return NULL;
}

int main(int argc, char *argv[])
{
    char inOrder[10000], postOrder[10000];
    scanf("%s", inOrder);
    scanf("%s", postOrder);
    Ird(inOrder, postOrder);
    return 0;
}
